// linkquence  queue

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct node
{
    int data;
    struct node *next;
} linklist_t;
typedef struct
{
    linklist_t *front;
    linklist_t *rear;
} linkqueue_t;

//空队列的概念：队头等于队尾
//为了区分满队和空对，队列元素个数要比数组元素个数少一个
//满队+1 等于空队
linkqueue_t *create_empty_linkqueue()
{
    linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t));
    linkqueue_t *q = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    q->front = q->rear = h;
    q->front->data = 0;
    return q;
}

int linkqueue_is_empty(linkqueue_t *q)
{
    return (q->front == q->rear);
}

//链式队列没有满的概念
/*
int linkqueue_is_full(linkqueue_t *q)
{

}
*/
int linkqueue_enqueue(linkqueue_t *q, int value)
{
    linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));
    p->data = value;
    p->next = q->rear->next;
    q->rear->next = p;
    q->rear = p;
    return 0;
}

//头部出列，头部删除法
int linkqueue_dequeue(linkqueue_t *q, int *pvalue)
{
    linklist_t *p;
    if (linkqueue_is_empty(q))
    {
        printf("列队为空");
        return -1;
    }

    p = q->front->next; //头节点的下一个节点，就是头
    //接上链表
    q->front->next = p->next;

    if (q->front->next == NULL) //如果删除的是最后一个节点，这时要手动让队头和队尾一致
    {
        q->rear = q->front; //此时队列为空，把队头和队尾设置一致
    }

    *pvalue = p->data;
    free(p);
    return 0;
}

int main(int argc, char const *argv[])
{
    linkqueue_t *Q = create_empty_linkqueue();

    printf("入队顺序为:");
    for (int i = 0; i < 32; i++)
    {
        if (linkqueue_enqueue(Q, i + 1) == 0)
        {
            printf("%d ", i + 1);
        }
    }
    printf("\n");

    printf("出队顺序为:");
    for (int i = 0, value; i < 33; i++)
    {
        if (linkqueue_dequeue(Q, &value) == 0)
        {
            printf("%d ", value);
        }
    }
    printf("\n");

    return 0;
}
